Eshan Chattopadhyay
Randomness is widely used in various areas of computer science, and many of the applications require uniform, uncorrelated bit. However, most sources of randomness in nature are defective and at best, only contain some amount of entropy. This leads to the area of randomness extraction, where an extractor is a deterministic procedure to produce pure random bits from a weak source. A central problem in this area is to extract from 2 independent weak sources (it is known that it is impossible to extract from just 1 weak source). This problem was raised by Chor and Goldreich, and Santha and Vazirani in the 80's.
In joint work with David Zuckerman, we resolve this problem. I will discuss the main ideas we use to solve this problem. Some of the ingredients that we use interestingly arise from cryptography and distributed computing.
As a corollary of our 2-source extractor, we obtain explicit constructions of Ramsey graphs within quasi-polynomial factors of the existential bound proved by Erdos in 1947, in his seminal paper introducing the probabilistic method. This is in a line of work spanning the last 67 years in an attempt to meet Erdos' challenge of matching the probabilistic bound.